﻿#define _CRT_SECURE_NO_WARNINGS

//DP-不同路径
class Solution {
private:
	int dfs(int i, int j, int m, int n) {
		if (i > m || j > n) return 0; // 越界了
		if (i == m && j == n) return 1; // 找到⼀种⽅法，相当于找到了叶⼦节点
		return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
	}
public:
	int uniquePaths(int m, int n) {
		return dfs(1, 1, m, n);
	}
};